package leetcode;

import java.util.Arrays;

/**
 * @Classname ThreeSumClosest
 * @Author happytaohaha
 * @Date 2020/3/1
 * @Description 最接近的三数之和
 * 和上一道题一样，借助了有序数组将问题简化
 */
public class ThreeSumClosest_0016 {
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        int sum = nums[0] + nums[1] + nums[2];
        int left;
        int right;
        for (int i = 0; i < len - 2; i++) {
            left = i + 1;
            right = len - 1;
            while (left < right) {
                int temp = nums[left] + nums[right] + nums[i];
                if (temp - target == 0) {
                    return target;
                }
                if (Math.abs(temp - target) < Math.abs(sum - target)) {
                    sum = temp;
                    continue;
                }
                if (temp - target > 0) {
                    right--;
                }
                if (temp - target < 0) {
                    left++;
                }
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(threeSumClosest(new int[]{-1,2,1,-4},1));
    }
}
